class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxBefore = [0 for _ in range(len(height))]
        maxAfter = [0 for _ in range(len(height))]

        maxSorFar = 0
        for i in range(len(height)):
            maxBefore[i] = maxSorFar
            maxSorFar = max(maxSorFar, height[i])
        maxSorFar = 0
        for i in range(len(height)-1, -1, -1):
            maxAfter[i] = maxSorFar
            maxSorFar = max(maxSorFar, height[i])
        water = 0
        for i in range(len(height)):
            bottom = height[i]
            top = min(maxBefore[i], maxAfter[i])
            water += max(0, top-bottom)
        return water

print(Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))